// 买卖股票的最佳时机含冷冻期
class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            //dp
            int n = prices.size();
            vector<vector<int>> dp(n,vector<int>(3));
            //dp[i][0]表示持有
            //dp[i][1] 不冷
            //dp[i][2] 冷冻
            dp[0][0] = -prices[0];
            for(int i = 1; i < n ;i++)
            {
                dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i]);
                dp[i][1] = max(dp[i-1][1],dp[i-1][2]);
                dp[i][2] = dp[i-1][0] + prices[i];
            }
            return max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
        }
    };

    // 买卖股票的最佳时机含手续费
    class Solution {
        public:
            int maxProfit(vector<int>& prices, int fee) {
                int n = prices.size();
                //dp[i][0] 持有
                //dp[i][1] 不持有
                vector<vector<int>> dp(n,vector<int>(2));
                dp[0][0] = -prices[0] - fee;
                for(int i = 1; i < n; i++)
                {
                    dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i] -fee);
                    dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i]);
                }
        
                return max(dp[n-1][0],dp[n-1][1]);
            }
        };